package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/insertion-sort-list/description/
 *
 * 147.链表插入排序
 *
 * 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
 *
 * 插入排序 算法的步骤:
 *
 * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 重复直到所有输入数据插入完为止。
 * 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
 *
 * 对链表进行插入排序。
 *
 * @author hanjuntao
 * @date 2025/8/1 0001
 */
public class L_147_insertion_sort_list {

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        ListNode result = insertionSortList(head);
        ListNode.print(result);

        
    }

    /**
     * 思路：
     *
     * 原先数组插入排序，是每次遍历到 一个元素时，将这个元素插入到已经排序的数组中。
     * 从当前位置往前遍历，如果当前元素小于前一个元素，交换两个元素的位置 。直至插入完成。
     *
     * 对于链表，由于是单向链表，无法从后往前遍历，只能从前往后遍历。所以每次从头节点遍历，插入到已排序的数组中。
     * 注意需要将原先的位置断开连接。
     *
     *
     * @param head
     * @return
     */
    public static ListNode insertionSortList(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;

        int i = 0;
        while (curr != null) {
            ListNode next = curr.next;

            // 如果当前元素大于前一个元素，那么说明现在的排序是正确的，不需要进行排序
            // 否则，将当前元素插入到已排序的数组中
            if (prev != null && prev.val > curr.val) {
                ListNode newHead = inertSort(curr, prev, head,  i);
                if (newHead != head) {
                    head = newHead;
                }
             } else {
                // 如果当前元素已插入到前面排序的链表中，则prev不再更新，原因是prev已指向curr的下一个元素，无需更新
                // 如果当前元素无需更新，那么正常向后走
                prev = curr;
            }

            curr = next;
            i++;
        }

        return head;
    }

    private static ListNode inertSort(ListNode waitInsert, ListNode waitInsertPrev, ListNode head, int i) {
        if (waitInsert == head) {
            return head;
        }

        int j = 0;
        ListNode curr = head;
        ListNode prev = null;

        while (curr != null) {
            // 遍历到当前元素时，停止遍历
            if (j == i) {
                break;
            }

            // 如果待插入的元素小于等于当前元素，则插入到当前元素前面
            ListNode next = curr.next;
            if (waitInsert.val <= curr.val) {
                // 断掉原先的节点
                if (waitInsertPrev != null) {
                    waitInsertPrev.next = waitInsert.next;
                }

                if (curr == head) {
                    head = waitInsert;
                    waitInsert.next = curr;
                } else {
                    // 上一个节点next指向新的节点
                    prev.next = waitInsert;
                    // 新节点next指向原先的节点
                    waitInsert.next = curr;
                }
                return head;
            }

            prev = curr;
            curr = next;
        }

        return head;
    }
}
